The present invention relates to technology mapping techniques for incomplete look-up tables, and more particularly, to techniques for determining functions in a circuit design can be implemented by incomplete lookup tables.
A lookup table is a memory circuit that stores binary bits of information. A lookup table can emulate a logic function that generates output values in response to receiving values of input signals. Each possible output of the logic function is stored in the lookup table at a memory address that matches corresponding values of the input signals.
A lookup table (LUT) can have any number of input terminals that receive input signals. A complete LUT has enough memory to store every (2N) binary value of its N input signals. For example, a complete 4 input LUT has enough memory to store 16 output bits that correspond to every binary value of the 4 input signals (24=16).
The term “incomplete LUT” is used to refer to a LUT that has less than 2N bits of memory to store output bits for every binary value of its N input signals. For example, a 5 input LUT can receive 25=32 possible binary values of its 5 input signals. A 5 input LUT is an incomplete LUT if it only has enough memory to store 16 different output bits.
Many reasonable configurations for incomplete LUTs have been made. For example, a 5 input incomplete LUT can be made from two 3 input LUTs and a multiplexer. The 3 input LUTs have two shared input signals. The fifth input signal controls the select terminal of the multiplexer. The multiplexer has two inputs that are coupled to the outputs of the LUTs.
A 7 input incomplete LUT can also be built from two 3 input LUTs and a multiplexer. The two 3 input LUTs have no shared input signals. The seventh input signal controls the select terminal of the multiplexer. The multiplexer has two inputs that are coupled to the outputs of the LUTs.
A different 7 input incomplete LUT can be built from a 5 LUT feeding a multiplexer. The LUT and sixth input signal feed the two data terminals of the multiplexer. The seventh input feeds the select terminal of the multiplexer.”
The number of functions that a LUT can implement equals 2M, where M is the number of storage bits in the LUT. However, not all of the functions that a complete LUT can implement are necessarily unique or useful. A complete 4 input LUT and the incomplete 5 input LUT described above can each implement 65536 functions. A complete 5 input LUT can implement about 4 billion functions.
The amount of area that is required to built a LUT on a silicon chip is proportional to the storage space in the LUT. An incomplete LUT uses far less silicon area than a complete LUT that has the same number of inputs, because incomplete LUTs have less storage space.
Technology mapping is a term that refers to the process of converting an arbitrary circuit design into an equivalent circuit that can be programmed onto a programmable integrated circuit such as field programmable gate array (FPGA). Most FPGAs use LUTs to implement logic functions. Technology mapping algorithms convert a circuit design into a network of available LUTs and other programmable circuit elements.
Traditional technology mapping algorithms operate on the assumption that all LUTs are complete in the sense described above. Such traditional algorithms assume, for example, that any 5 input function can be implemented in a 5 input LUT.
However, it may not be possible to implement a 5 input logic function in an incomplete 5 input LUT. An incomplete 5 input LUT may not have enough memory storage space to store all of the possible output values of a 5 input function.
It would be desirable to use incomplete LUTs in technology mapping tools, because incomplete LUTs can implement functions using less storage space than complete LUTs having the same number of inputs. Therefore, it would be desirable to provide technology mapping techniques that determine whether functions in a circuit design can be fully implemented using incomplete LUTs.